/**
 *  Merge Sort
 *
 *  Time complexity:
 *  Space complexity:
 *
 */

import java.util.ArrayList;

class MergeSort2<E extends Comparable<E>> {

    public E[] sort(E[] a, int lo, int hi) {
        ArrayList<E> list = new ArrayList<E>();

        if (lo > hi) {
            return list2Array(list);
        } else if (lo == hi) {
            list.add(a[lo]);
            return list2Array(list);
        } else {
            int mid = lo + (hi - lo) / 2;
            
            E[] a1 = sort(a, lo, mid);
            E[] a2 = sort(a, mid + 1, hi);
            
            return merge(a1, a2);
        }
    }

    private E[] merge(E[] a1, E[] a2) {
        ArrayList<E> list = new ArrayList<E>();

        int i1 = 0;
        int i2 = 0;

        E v1;
        E v2;

        while (i1 < a1.length && i2 < a2.length) {
            v1 = a1[i1];
            v2 = a2[i2];

            if (v1.compareTo(v2) < 0) {
                list.add(v1);
                i1++;
            } else {
                list.add(v2);
                i2++;
            }
        }

        while (i1 < a1.length) {
            v1 = a1[i1++];
            list.add(v1);
        }

        while (i2 < a2.length) {
            v2 = a2[i2++];
            list.add(v2);
        }

        return list2Array(list);
    }

    private E[] list2Array(ArrayList<E> list) {
        return (E[]) list.toArray((E[]) new Comparable[list.size()]);
    }

}
